/*
 * @Descripttion: 235. 二叉搜索树的最近公共祖先
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
 * @Author: yubo
 * @Date: 2022-09-26 15:37:58
 * @LastEditTime: 2022-09-26 17:29:31
 */
#pragma once

#include "../Base/TreeNode.h"

#include <map>

namespace Solution_235
{
    class Solution
    {
    public:
        TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
        {
            vector<TreeNode *> pPath = GetPath(root, p);
            vector<TreeNode *> qPath = GetPath(root, q);

            TreeNode *ans = nullptr;
            for (size_t i = 0; i < pPath.size() && i < qPath.size(); ++i)
            {
                if (pPath[i] != qPath[i])
                {
                    break;
                }
                //要取最深的公共节点，所以要尽量往后遍历
                ans = pPath[i];
            }

            return ans;
        }

    private:
        //遍历找到节点，返回path上所有的节点
        vector<TreeNode *> GetPath(TreeNode *root, TreeNode *node)
        {
            vector<TreeNode *> result;
            TreeNode *iter = root;
            while (iter != nullptr)
            {
                result.push_back(iter);
                if (iter->val == node->val)
                {
                    break;
                }

                if (node->val < iter->val)
                {
                    iter = iter->left;
                }
                else
                {
                    iter = iter->right;
                }
            }
            return result;
        }
    };

    void Test()
    {
        std::vector<int> src{6, 2, 8, 0, 4, 7, 9, NULL_VALUE, NULL_VALUE, 3, 5};
        TreeNode *root = GenerateTreeNode(src);

        TreeNode p(2);
        TreeNode q(4);

        Solution solv;
        auto result = solv.lowestCommonAncestor(root, &p, &q);
        cout << result->val << endl;
    }
}